'''
难度:中等
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: nums =  [3,3,7,7,10,11,11]
输出: 10
提示:
1 <= nums.length <= 105
0 <= nums[i] <= 105
 进阶: 采用的方案可以在 O(log n) 时间复杂度和 O(1) 空间复杂度中运行吗？
'''


'''
**

```
Example 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: [3,3,7,7,10,11,11]
Output: 10
```
**分析：** 异或的巧妙应用！
如果mid是偶数，那么和1异或的话，那么得到的是mid+1，
如果mid是奇数，得到的是mid-1。
如果相等的话，那么唯一的元素还在这之后，
往后找就可以了。
'''
from typing import List


class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l,r = 0,len(nums)-1
        while l<r:
            mid = (l+r)//2
            if nums[mid] == nums[mid^1]:
                l = mid + 1
            else:
                r =mid
        return nums[l]
